/**
 * Vector is a mutable, dynamically-resizing wrapper around Array. Vectors start
 * with a capacity and a length of 0; when their length exceeds their capacity,
 * a new vector will be allocated.
 */
struct Vector[T] {
    var allocator: Box[Allocator];
    public var length: Size;
    var data: Array[T];

    public static function new(allocator: Box[Allocator], capacity: Size = 16): Vector[T] using implicit allocator {
        if capacity < 4 {
            capacity = 4;
        }
        return struct Self {
            allocator,
            length: 0,
            data: Array.new(capacity),
        };
    }

    public function free(): Void using implicit this.allocator {
        this.data.free();
    }

    public function push(value: T): T {
        this.ensureSize(this.length + 1);
        return this[this.length++] = value;
    }

    public function pop(): Option[T] {
        if this.length > 0 {
            return Some(this[--this.length]);
        } else {
            return None;
        }
    }

    public function grow(): Ptr[T] {
        this.ensureSize(this.length + 1);
        return &(this[this.length++]);
    }

    public function concat(other: Vector[T]): Vector[T] {
        var newVector = Self.new(this.length + other.length);
        for i in 0 ... this.length {
            newVector.push(this[i]);
        }
        for i in 0 ... other.length {
            newVector.push(other[i]);
        }
        return newVector;
    }

    public function clear(): Void {
        this.length = 0;
    }

    public function ensureSize(n: Size): Void {
        var l = this.data.length;
        if l < n {
            if l < 1 {
                l = 1;
            }
            do {
                l = (l * 1.5) as Size;
            } while l < n;
            // resize and swap the underlying data of the vector
            var newData: Ptr[T] = this.allocator.alloc(l * sizeof T);
            var oldData = this.data.data;
            memcpy(newData, oldData, this.length * sizeof T);
            this.data.length = l;
            this.data.data = newData;
            this.allocator.free(oldData);
        }
    }

    public function ref(): Ptr[T] {
        return this.data.data;
    }

    public function slice(): Slice[T] {
        return struct Slice[T] {length: this.length, data: this.ref()};
    }

    public function removeAt(i: Int): T {
        var val = this.data.data[i];
        if i < this.length - 1 {
            memcpy(&this.data.data[i], &this.data.data[i + 1], (this.length - i) * sizeof T);
        }
        --this.length;
        return val;
    }

    public function all(fn: function (&T) -> Bool): Bool {
        for item in this {
            if !fn(item) {
                return false;
            }
        }
        return true;
    }

    public function any(fn: function (&T) -> Bool): Bool {
        for item in this {
            if fn(item) {
                return true;
            }
        }
        return false;
    }

    rules {
        ($this :: ${other: Self}) => $this.concat(other);
        // FIXME: implement term rewriting for casts
        ($this as Slice[T]) => struct Slice[T] {length: $this.length, data: $this.ref()};

        /**
         * Returns the first element in the Vector, or None if the Vector is empty.
         */
        ($this.first) => if _length > 0 then Some($this[0]) else None;
        ($this.unsafeFirst) => $this[0];

        /**
         * Returns the last element in the Vector, or None if the Vector is empty.
         */
        ($this.last) => if $this.length > 0 then Some($this[$this.length - 1]) else None;
        ($this.unsafeLast) => $this[$this.length - 1];

        ($this[$i]) => $this.data[$i];

        ($this.capacity) => $this.data.length;

        // optimize Vector iteration at compile time when the type is known
        (for $ident in $this {$e}) => {
            var __length = $this.length;
            for __i in 0 ... __length {
                var $ident = $this[__i];
                {$e}
            }
        }
    }
}

// implement Iterable[T] for Vector[T] {
//     public function iterator() {
//         return VectorIterator.new(this);
//     }
// }

// struct VectorIterator[T] {
//     public var index: Uint;
//     public var Vector: Ptr[Vector[T]];

//     public static function new(Vector: Ptr[Vector[T]]) {
//         return struct Self {
//             Vector,
//             index: 0
//         };
//     }
// }

// implement Iterator[T] for VectorIterator[T] {
//     public function next(): Null[T] {
//         return if index < Vector.length {
//             Some(Vector[index++]);
//         } else {
//             None;
//         }
//     }
// }
